1946B - Maximum Sum - CodeForces Solution

tc = int(input())
MOD = int(1e9 + 7)
for case in range(tc):
    n,k = tuple(map(int, input().split()))
    nums = list(map(int, input().split()))
    best_sum = 0
    actual_contiguous_sum = 0
    left = -1
    for i in range(n):
        cur_num = nums[i]
        if actual_contiguous_sum + cur_num > cur_num:
            actual_contiguous_sum += cur_num
        else:
            left = i
            actual_contiguous_sum = cur_num
        best_sum = max(best_sum, actual_contiguous_sum)
    last_best_cont = sum(nums[left:])
        total = 0
    for num in nums:
        total = (total+num)%MOD
            for j in range(k):
        total = (total + best_sum)%MOD
        best_sum = (best_sum+best_sum)%MOD
                
        
    print(total)